import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Intersection {
//    public static void main(String[] args) {
//        Solution2 solution1 = new Solution2();
//        int a[] = {4,9,5};
//        int b[] = {9,4,9,8,4};
//        int[] ss = solution1.intersection(a,b);
//        for (int i = 0; i <ss.length ; i++) {
//            System.out.println(ss[i]);
//        }
//
//    }
public static void main(String[] args) {
    Soltion solution1 = new Soltion();
    int [] a = {4,9,5};
    int [] b = {9,4,9,8,4};
    int[] ss = solution1.intersection(a,b);
    for (int i = 0; i <ss.length ; i++) {
        System.out.println(ss[i]);
    }

}
}

/**
 * 两个数组的交集
 * 题目描述
 *      给定两个数组，编辑一个函数来计算他们的交集
 *      示列1：
 *          输入：nums1 = [1,2,2,1], nums2 = [2,2]
 *          输出：[2]
 *      示列2：
 *          输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 *          输出：[9,4]
 *      说明:
 *          输出结果中的每个元素一定是唯一的。
 *          我们可以不考虑输出的结果。
 *
 *      解法一
 *      思路：
 *          幼稚的方法是根据第一个数组nums1迭代并检查每个值是否存在在nums2内。如果存在就添加到输出。
 *          这样的方法会导致O(n*m)的时间复杂度，其中n和m是数组的长度。
 *
 *          为了在线性时间内解决这个问题，我们使用集合set，在O(1)时间复杂度实现操作
 *
 *          其思想是将两个数组转换为集合set，然后迭代较小的集合检查是否存在较大集合中。这种方法的时间复杂度为O(n+m).
 *
 */
//class Solution2 {
//    public int[] set_intersection(HashSet<Integer> set1, HashSet<Integer> set2){
//        int[] output = new int[set1.size()];
//        int idx = 0;
//        for (Integer s:set1){
//            if (set2.contains(s)){
//                output[idx++] = s;
//            }
//        }
//        return Arrays.copyOf(output,idx);
//    }
//
//    public int[] intersection(int[] nums1, int[] nums2) {
//        HashSet<Integer>set1 = new HashSet<Integer>();
//        for (Integer n : nums1){
//            set1.add(n);
//        }
//        HashSet<Integer> set2 = new HashSet<Integer>();
//        for (Integer n : nums2){
//            set2.add(n);
//        }
//        if (set1.size() < set2.size()){
//            return set_intersection(set1,set2);
//        }else {
//            return set_intersection(set2,set1);
//        }
//    }
//}


/**
 * 两个数组的交集
 * 题目描述
 *      给定两个数组，编辑一个函数来计算他们的交集
 *      示列1：
 *          输入：nums1 = [1,2,2,1], nums2 = [2,2]
 *          输出：[2]
 *      示列2：
 *          输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 *          输出：[9,4]
 *      说明:
 *          输出结果中的每个元素一定是唯一的。
 *          我们可以不考虑输出的结果。
 *
 *      解法二
 *      思路：
 *      内置的函数在一般情况下的时间复杂度是 O(n+m)O(n+m) 且时间复杂度最坏的情况是 O(n \times m)O(n×m) 。
 *
 *      在 Python 中提供了交集的操作，在 Java 提供了 retainAll() 函数.
 */
class Soltion{
    public int[]intersection(int[] nums1, int[] nums2){
        HashSet<Integer> set1 = new HashSet<Integer>();
        for (Integer n : nums1) {
            set1.add(n);
        }
        HashSet<Integer> set2 = new HashSet<Integer>();
        for (Integer n: nums2) {
            set2.add(n);
        }
        set1.retainAll(set2);
        int[] output = new int[set1.size()];
        int idx = 0;
        for (int s: set1) {
            output[idx++]=s;
        }
        return output;
    }
}